package org.usmile.algorithms.leetcode.middle;

/**
 * 666. 路径总和 IV
 *
 * 对于一棵深度小于 5 的树，可以用一组三位十进制整数来表示。对于每个整数：
 * 百位上的数字表示这个节点的深度 d，1 <= d <= 4。
 * 十位上的数字表示这个节点在当前层所在的位置 P， 1 <= p <= 8。位置编号与一棵满二叉树的位置编号相同。
 * 个位上的数字表示这个节点的权值 v，0 <= v <= 9。
 * 给定一个包含三位整数的 升序 数组 nums ，表示一棵深度小于 5 的二叉树，请你返回 从根到所有叶子结点的路径之和 。
 * 保证 给定的数组表示一个有效的连接二叉树。
 *
 * 示例 1：
 * 输入: nums = [113, 215, 221]
 * 输出: 12
 * 解释: 列表所表示的树如上所示。
 * 路径和 = (3 + 5) + (3 + 1) = 12.
 *
 * 示例 2：
 * 输入: nums = [113, 221]
 * 输出: 4
 * 解释: 列表所表示的树如上所示。
 * 路径和 = (3 + 1) = 4.
 *
 * 提示:
 * 1 <= nums.length <= 15
 * 110 <= nums[i] <= 489
 * nums 表示深度小于 5 的有效二叉树
 */
public class _0666 {
}

class _0666_Solution {
    private int ans = 0;
    public int pathSum(int[] nums) {
        // 构建二叉树，使用数组存储
        Integer[] tree = new Integer[15];
        for (int num : nums) {
            int level = num / 100;
            int levelIndex = num % 100 / 10;
            int val = num % 10;
            int index = ((1 << (level - 1)) - 1) + levelIndex - 1;
            tree[index] = val;
        }

        // DFS 遍历树
        dfs(tree, 0, 0);

        return ans;
    }

    private void dfs(Integer[] tree, int i, int currPathSum) {
        if (tree[i] == null) {
            return;
        }

        currPathSum += tree[i];
        if (i >= 7 || (tree[2 * i + 1] == null && tree[2 * i + 2] == null)) {
            ans += currPathSum;

            return;
        }

        dfs(tree, 2 * i + 1, currPathSum);
        dfs(tree, 2 * i + 2, currPathSum);
    }
}